package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/description/">对称的二叉树</a>
 * <p>请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。</p>
 * <pre>
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *     1
 *
 *    / \
 *
 *   2   2
 *
 *  / \ / \
 *
 * 3  4 4  3
 *
 *
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *     1
 *
 *    / \
 *
 *   2   2
 *
 *    \   \
 *
 *    3    3
 * </pre>
 *
 * @author c2b
 * @since 2023/3/27 9:40
 */
public class JzOffer0028IsSymmetric_S {

    public boolean isSymmetric(final TreeNode root) {
        if (root == null) {
            return true;
        }
        // 利用同一个队列，每次入列与出队两个元素
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode pollNode1 = queue.poll();
            TreeNode pollNode2 = queue.poll();
            if (pollNode1 == null && pollNode2 == null) {
                continue;
            }
            if (pollNode1 == null || pollNode2 == null || pollNode1.val != pollNode2.val) {
                return false;
            }
            // 按照相反顺序入队
            queue.offer(pollNode1.left);
            queue.offer(pollNode2.right);
            queue.offer(pollNode1.right);
            queue.offer(pollNode2.left);
        }
        return true;
    }

    public boolean isSymmetric1(final TreeNode root) {
        return root == null || recursion(root.left, root.right);
    }

    // 递归
    private boolean recursion(TreeNode u, TreeNode v) {
        if (u == null && v == null) {
            return true;
        }
        if (u == null || v == null || u.val != v.val) {
            return false;
        }
        return recursion(u.right, v.left) && recursion(u.left, v.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(new JzOffer0028IsSymmetric_S().isSymmetric(root));
        System.out.println(new JzOffer0028IsSymmetric_S().isSymmetric1(root));
    }
}
